package cn.hy.机考.part03;

import java.util.*;

/**
 * @author hy
 *
 * 二十、单词接龙
 * 可用于接龙的单词首字母必须要与前一个单词的尾字母相同。
 * 当存在多个首字母 相同的单词时，取长度最长的单词 如果长度也相等则取词典序最小的单词。
 * 已经参与接龙的单词不能重复使用 现给定一组全部由小写字母组成的单词数组，并指定其中的一个单词为起始单词 进行单词接龙。
 * 请输出最长的单词串，单词串是由单词拼接而成 中间没有空格
 * 输入的第一行为一个非负整数，表示起始单词在数组中的索引k 0<=k<=n 第二行输入的是一个非负整数表示单词的个数 n，接下来的 n 行分别表示单词数 组中的单词
 * 输出一个字符串表示最终拼接的字符串
 * 0
 * 6
 * word
 * dd
 * da
 * dc
 * dword
 * d
 * 输出:worddwordda
 * 先确定起始单词 word，再确定 d 开头长度最长的单词 dword，剩余以 d 开头且长 度最长的由 da dd dc，则取字典序最小的 da
 * 所以最后输出 worddwordda
 */
public class Demo20 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {

            int index = Integer.parseInt(sc.nextLine());
            int num = Integer.parseInt(sc.nextLine());
            List<String> list = new ArrayList<>();
            for (int i = 0 ; i < num ; i++) {
                list.add(sc.nextLine());
            }

            //加入到字符串中
            StringBuilder sb = new StringBuilder();
            sb.append(list.get(index));
            list.remove(index);

            list.sort(new Comparator<String>() {
                @Override
                public int compare(String w1, String w2) {
                    int len1 = w1.length();
                    int len2 = w2.length();
                    if (len1 == len2) {
                        return w1.compareTo(w2);
                    } else {
                        return len2 - len1;
                    }
                }
            });

            int len = 0;
            do {
                len = sb.length();
                String last = sb.substring(sb.length() - 1); // 取最后一个字符
                Iterator<String> iterator = list.iterator();
                while (iterator.hasNext()) {
                    String begin = iterator.next();
                    if (begin.startsWith(last)) {
                        sb.append(begin);
                        iterator.remove();
                        break;
                    }
                }
                // 如果长度没有变动， 说明已经找到最长的
            } while (sb.length() != len);

            System.out.println(sb.toString());
        }
    }
}
